package com.sicheng.lc.周赛.分类.哈西表or计数or滑动窗口or双指针.滑动窗口;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/4 21:53
 */
public class 最少交换次数来组合所有的1 {
    //https://leetcode.cn/problems/minimum-swaps-to-group-all-1s-together-ii/
    public int minSwaps(int[] nums) {
        int sum = 0;

        for (int num : nums) {
            sum += num;
        }
        if (sum == nums.length)
            return 0;
        int l = 0, r = sum - 1;
        int t = 0;
        for (int i = l; i <= r; i++) {
            if (nums[i] == 0)
                t++;
        }
        int min = t;
        while (l < nums.length) {
            if (nums[l] == 0)
                t--;
            l = (l + 1);
            r = (r + 1) % nums.length;
            if (nums[r] == 0)
                t++;
            min = Math.min(min, t);
        }

        return min;
    }

    public static void main(String[] args) {
        最少交换次数来组合所有的1 s = new 最少交换次数来组合所有的1();
        int[] nums = {
                0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0,
                0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0,
                0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1,
                0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0,
                1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
                1, 0, 0};
        System.out.println(s.minSwaps(nums));
    }
}
